package com.sen.auth.service;

import org.bouncycastle.jcajce.provider.digest.SHA512;
import org.omg.CORBA.Any;

import java.util.Comparator;
import java.util.TreeSet;

/**
 * Created by lsyuan on 2018/2/23.
 */
public class MyBalancedTree<AnyType extends Comparable> {

    private Node<AnyType> root;
    private long size;
    private int ALLOWED_HEIGHT = 1;
    private Comparator comparator;

    public MyBalancedTree() {
        clear();
    }

    public MyBalancedTree(Comparator cmp) {
        clear();
        comparator = cmp;
    }

    private class Node<AnyType>{

        private AnyType data;
        private Node<AnyType> left;
        private Node<AnyType> right;
        private int height;

        private Node(AnyType data) {
            this(data,null,null,0);
        }

        private Node(AnyType data, Node<AnyType> left, Node<AnyType> right, int height) {
            this.data = data;
            this.left = left;
            this.right = right;
            this.height = height;
        }
    }

    public class MyComparactor implements Comparator<AnyType>{
        @Override
        public int compare(AnyType o1, AnyType o2) {
            return o1.compareTo(o2);
        }
    }

    private int height(Node<AnyType> node){
        if(node == null){
            return -1;
        }
        return node.height;
    }

    public void clear(){
        doClear(root);
        size = 0;
    }

    public void doClear(Node<AnyType> node){
        node = new Node<AnyType>(null);
    }

    public void add(AnyType data){
        Comparator cmp = comparator == null ? new MyComparactor() : comparator;
        root = insert(data,root,cmp);
    }

    public void printTree(){
        printTree(root);
    }

    public void printTree(Node<AnyType> node){
        if(node == null){
            return;
        }
        printTree(node.left);
        System.out.println(node.data);
        printTree(node.right);
    }

    public Node<AnyType> insert(AnyType data,Node<AnyType> node){
       return insert(data,node,new MyComparactor());
    }

    public Node<AnyType> insert(AnyType data,Node<AnyType> node,Comparator cmp){
        if(node == null){
            return new Node<AnyType>(data);
        }
        int cmpNum = cmp.compare(node.data,data);
        if(cmpNum < 0){
            node.left = insert(data,node.left,cmp);
        }else if (cmpNum > 0){
            node.right = insert(data,node.right,cmp);
        }else{
            ;
        }
        node.height = Math.max(height(node.left),height(node.right)) + 1;
        return balance(node);
    }

    public Node<AnyType> balance(Node<AnyType> node){
        if(node == null){
            return node;
        }
        if(height(node.left) - height(node.right) > ALLOWED_HEIGHT){
            if(height(node.left.left) >= height(node.left.right)){
                node = rotateWithLeftChild(node);
            }else{
                node = doubleWithLeftChild(node);
            }
        }else if(height(node.right) - height(node.left) > ALLOWED_HEIGHT){
            if(height(node.right.right) >= height(node.right.left)){
                node = rotateWithRightChild(node);
            }else{
                node = doubleWithRightChild(node);
            }
        }
        return node;
    }

    private Node<AnyType> rotateWithLeftChild(Node<AnyType> k1){
        Node<AnyType> k2 = k1.left;
        k1.left = k2.right;
        k2.right = k1;
        k1.height = Math.max(height(k1.left),height(k1.right)) + 1;
        k2.height = Math.max(height(k2.left),height(k1)) + 1;
        return k2;
    }

    private Node<AnyType> doubleWithLeftChild(Node<AnyType> k1){
        k1.left = rotateWithRightChild(k1.left);
        return rotateWithLeftChild(k1);
    }

    private Node<AnyType> rotateWithRightChild(Node<AnyType> k1){
        Node<AnyType> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = Math.max(height(k1.left),height(k1.right)) + 1;
        k2.height = Math.max(height(k1),height(k2.right)) + 1;
        return k2;
    }

    private Node<AnyType> doubleWithRightChild(Node<AnyType> k1){
        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);
    }
}
